<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>
<body>
    <script>
        // 非循环引用测例
        // let obj = {}, obj2 = {};
        // obj.a = obj2; // obj2 => obj
        // obj.b = { obj2 }; // obj2 => {} => obj

        // 循环引用测例
        let obj = {}, obj2 = {}; // obj: { a: { b: obj } }
        obj.a = obj2;
        obj2.b = obj;
        function hasCircle(obj) {
            let result = false;
            let ws = new WeakSet(); // 此WeakSet里存放的对象表示：某个属性被检查前它的所有父级对象
            // walk(obj)表示考察obj对象的属性，检查是否存在循环引用
            // 递归函数准确定义：考察obj的所有属性之前，obj的所有父级元素出于ws中
            const walk = (obj) => {
                ws.add(obj); // 首先obj放入WeakSet中
                for(let key of Object.keys(obj)) {
                    let value = obj[key];
                    if(typeof value === 'object') { // 只检测对象类型
                        if(ws.has(value)) {
                            result = true;
                        } else {
                            walk(value);
                        }
                    }
                }
                // 已经检查完所有属性，删除obj，因为该检查与obj同层级的其它obj的属性了，所以obj已经不是那些属性的父级对象了，需要删除
                ws.delete(obj);
            }
            walk(obj, ws);
            return result;
        }

        // 上面的算法因为所有递归逻辑都共用一个WeakSet对象，所以需要有一个回溯的过程。如下算法实现更为直观
        function hasCircle2(obj) {
            let result = false;
            // 检查obj的属性是否存在循环引用，parentArr为其属性的所有父对象（检查obj的属性之前，已经把obj放入parentArr中了）
            const walk = (obj, parentArr) => {
                for(let key of Object.keys(obj)) {
                    let value = obj[key];
                    console.log(value);
                    if(typeof value === 'object') { 
                        // 用一个循环去找寻parent数组中是否存在value对象，存在即为循环引用
                        for(let i = 0; i < parentArr.length; i ++) {
                            if(parentArr[i] === value) {
                                result = true;
                            }
                        }
                        if(result === false) {
                            walk(value, [...parentArr, value]);
                        }
                    }
                }
            }
            walk(obj, [obj]);
            return result;
        }
        console.log(hasCircle(obj));
        console.log(hasCircle2(obj));
    </script>
</body>
</html>